\subsection{Übungsblatt 5 - Signaturen}
\subsubsection{Übung i \buchmann{13.9.1}}
Aufgabe: Berechnen Sie die RSA-Signatur (ohne Hashfunktion) von $m=11111$ mit RSA-Modul $n=28829$ und dem kleinstmöglichen öffentlichen Exponenten $e$.\\
$$p=127, n=227, n=p*q, n=127*227=28829$$
$$ggT(e,(p-1)(q-1))=1$$
\begin{center}
\underline{$e=5$} und nicht $e=3$, da $3$ ein Teiler von $28476$ ist.\\
\end{center}
$$e*d\equiv1\tmod{((p-1)(q-1))}$$
$$e*d+(p-1)*(q-1)*x=1$$
\begin{center}
Lösung über den erweiterten euklidischen Algorithmus\\
\end{center}
\begin{center}
\begin{tabular}{c|c|c|c}
 & 0 & 1 & 2 \\
\hline
r & 28746 & 5 & 1\\
q & & 5695 & 5\\
x & 1 & 0 & 1\\
y & 0 & 1 & -5695\\

\end{tabular}
\end{center}
$$5*(-5695)+28476*1=1$$
$$\underline{d}=-5695+28746=\underline{22781}$$
$$s=m^{d}\tmod{n}$$
$$s=11111^{22781}\tmod{28829}$$

\begin{center}
Die Binärdarstellung von $22781$ ist $101100011111101$\\
Lösung mittels Square and Multiply\\
\end{center}

$$ 11111^{2^0} = 11111 $$
$$ 11111^{2^1} = 11111^{2} \equiv 8543 $$
$$ 11111^{2^2} = 8543^{2} \equiv 16650 $$
$$ 11111^{2^3} = 16650^{2} \equiv 2836 $$
$$ 11111^{2^4} = 2836^{2} \equiv 28434 $$
$$ 11111^{2^5} = 28434^{2} \equiv 11880 $$
$$ 11111^{2^6} = 11880^{2} \equiv 16445 $$
$$ 11111^{2^7} = 16445^{2} \equiv 22005 $$
$$ 11111^{2^8} = 22005^{2} \equiv 8141 $$
$$ 11111^{2^9} = 8141^{2} \equiv 26839 $$
$$ 11111^{2^{10}} = 26839^{2} \equiv 10527 $$
$$ 11111^{2^{11}} = 10527^{2} \equiv 27882 $$
$$ 11111^{2^{12}} = 27882^{2} \equiv 3110 $$
$$ 11111^{2^{13}} = 3110^{2} \equiv 14385 $$
$$ 11111^{2^{14}} = 14385^{2} \equiv 22492 $$

$$22492*3110*27882*22005*16445*11880*28434*2836*16550*11111\tmod{28829}\equiv7003\tmod{28829}$$
$$\underline{s=7003}$$
\\\\
Als Optimierung kann die Aufgabe mit dem chinesischen Restsatz und der Rechnung \textit{modulo p} und \textit{modulo q} gelöst werden.

$$\underline{s\textsubscript{p}}=11111^{22781} \equiv 11111^{22781 \mod 126} \equiv 11111^{101} \equiv \underline{18} \mod 127$$
$$\underline{s\textsubscript{q}}=11111^{22781} \equiv 11111^{22781 \mod 226} \equiv \underline{193} \mod 227$$

\begin{center}
Mit dem euklidischen Algorithmus kann $y\textsubscript{p}*p+y\textsubscript{q}*q=1$ gelöst werden
\end{center}
$$\underline{y\textsubscript{p}=-84}$$
$$\underline{y\textsubscript{q}=47}$$\\
$$s=s\textsubscript{p}*y\textsubscript{q}*q+s\textsubscript{q}*y\textsubscript{p}*p\tmod{n}$$
$$\underline{s}=18*47*227+193*(-84)*127 \equiv \underline{7003} \tmod 28829$$




\subsubsection{Übung ii \buchmann{13.9.7}}
Zunächst muss für den öffentlichen Schlüssel $A$ berechnet werden. Es gilt $A=g^a\mod{p}$. In diesem Beispiel also:
$$A=2^{1234}\mod{2237}$$
$$2^{1234}\equiv 10\mod{2237}$$
Damit ergibt sich für den öffentlichen Schlüssel $(p,g,A)$ der Wert $(2237,2,10)$.\par
Im nächsten Schritt wird die Signatur berechnet. Dazu wird $k$ zufällig gewählt mit $\gcd{(k,p-1)}=1$. In der Aufgabenstellung ist $k$ mit $2323$ vorgegeben.
Die Bedingung $\gcd(2323,2236)=1$ ist erfüllt. Der Hashwert der Nachricht $m$ ist $h(m)=111$. Nun werden die Werte $r$ und $s$ berechnet. Für $r$ gilt $r=g^k\mod{p}$:
$$r=2^{2323}\mod{2237}=799$$
Zusätzlich wird s berechnet. Dafür wird $k^{-1}\mod{(p-1)}$ benötigt. Dies lässt sich mit dem erweiterten euklidschen Algorithmus berechnen. Für $k^{-1}\mod{2236}$ ergibt sich der Wert $1979$.
$s$ lässt sich mit $s=k^{-1}(h(m)-ar)\mod{(p-1)}$ berechnen:
$$s=1979*(111-10*799)\mod{2236}=1323\mod{2236}$$
Damit ergibt sich für die Signatur $(r,s)$ der Wert $(799,1339)$.\par
Nun wird die Verifikation durchgeführt. Zunächst wird geprüft, ob $1\leq r\leq 2236$ gilt. Da $r=799$ ist, ist diese Bedingung erfüllt.
Anschließend wird die Verifikationskongruenz $A^rr^s\equiv g^{h(x)}\mod{p}$ überprüft.
$$10^{799}*799^{1339}\mod{2237}\equiv 1258$$
$$2^{111}\mod{2237}\equiv 1258$$
Damit ist die Verifikationskongruenz erfüllt und die Signatur akzeptiert.
\subsubsection{Übung iii \buchmann{13.9.8}}
Die Signatur der alten Nachricht $(r,s)$ ist $(799,1339)$.
Zunächst muss $u$ berechnet werden. Für die Berechnung von $u$ gilt $u=h(x')h(x)^{-1}\mod{(p-1)}$. Dafür muss $h(x)$ invertierbar mod$(p-1)$ sein.
Dies ist in dieser Aufgabe möglich. Das Inverse von $111\mod{2236}$ ist $2095$. Damit ergibt sich für $u$:
$$u=99*2095\mod{2236}=1693$$
Mit Hilfe von $u$ lässt sich nun $s'$ berechnen:
$$s'=su\mod{(p-1)}=1339*1693\mod{(2236)}=1859$$
Zur Berechnung von $r'$ müssen diese simultanen Kongruenzen erfüllt werden:
$$r'\equiv ru\mod{(p-1)}$$
$$r'\equiv r\mod{p}$$
$$r'\equiv 799*1693\mod{2236}\equiv 2163\mod{2236}$$
$$r'\equiv 799\mod{2237}$$
Mit Hilfe des chinesischen Restsatzes lassen sich diese berechnen.
Zunächst muss $M$ berechnet werden: $M=2236*2237=5001932$. Mit Hilfe von $M$ lässt sich $M_1$ und $M_2$ berechnen:
$$M_1=5001932/2236=2237$$
$$M_2=5001932/2237=2236$$
Es muss die Gleichung $\alpha (p-1) + \beta p = 1$ gelöst werden. Man sieht direkt, dass $\alpha = -1, \beta = 1$ eine Lösung ist.
Lösung der Kongruenz ist dann $r' = 2163 * \beta * p + 799 * \alpha * (p-1) = 2163 * 2237 - 799 * 2236 = 3052067$.
Mit $r'=3052067$ sind die beiden Kongruenzen erfüllt. Die gefälschte Signatur $(r',s')$ ist demnach $(3052067, 1859)$.
Mit der Verifikationskongruenz kann nun überprüft werden, ob diese errechnete Signatur ebenfalls gültig ist:
$$A^{r'}(r')^{s'}\equiv g^{h(m')}\mod{p}$$
$$10^{3052067}*3052067^{1859}\equiv 2210\mod{2237}$$
$$2^{99}\equiv 2210\mod{2237}$$
Die gefälschte Signatur erfüllt damit ebenfalls die Verifikationskongruenz, würde aber gegen die Bedingung $1\leq{r}\leq{p-1}$ verstoßen.

\subsubsection{Übung iv}

Es sei $H$ eine Hashfunktion mit $l$ Bit langen Hashwerten, die Sie in einem Merkle-Signaturverfahren
mit LD-OTS verwenden. Der Wert $r$ ist gleich $l$, wie es das LD-OTS Verfahren verlangt.
Die Höhe des Binärbaumes beginnt bei $0$.

\begin{enumerate}

\item Wie viel Speicherplatz benötigen Sie als Inhaber der Signaturschlüssel, wenn der Hashbaum die Höhe $h$ hat?

Es wird angenommen, dass der ganze Hashbaum gespeichert wird d.h. Wurzel und alle Knoten inklusive der Blätter.

Für die Speicheraufwände gilt daher: 

\begin{itemize}
  \item Wurzel + Knoten + Blätter : $2^{h+1}-1$ 
  \item Blätter: $2^h$
  \item Signaturschlüsselpaar bestehend aus $x(0,1), x(1,1), \ldots, x(0,r), x(1,r)$ und $y(i,j) = H(x(i,j))$ für $0 \le i \le 1, 1 \le j \le r$ (Signatur- und Verifikationsschlüssel: $(2 \cdot r \cdot l)+(2 \cdot r \cdot l)=4 \cdot r \cdot l$ Bits
\end{itemize}

Speicheraufwand gesamt:

\begin{align*}
(2^{h+1}-1) \cdot l + (2^h) \cdot (4 \cdot r \cdot l) \approx 2^{h+2}r\ell 
\end{align*}

\item Wie viele Bits umfassen eine konkrete LD-OTS und die Verifikationsdaten?

Die Verifikationsdaten sind gegeben durch: $(i,y_i,s,(a_h,\ldots,a_1))$

Für die Speicheraufwände gilt:

\begin{itemize}
  \item Index $i$ gegeben durch  $0 \le i < 2^h$: $h$ Bits
  \item Verifikationsschlüssel $y_i$: $2 \cdot r \cdot l$ Bits
  \item Signatur $s$: $r \cdot l$ Bits
  \item Authorisationspfad $(a_h,\ldots,a_1)$: $h \cdot l$ Bits
\end{itemize}

Signaturgröße gesamt:

\begin{align*}
h + (2\cdot r \cdot l) + (r \cdot l) + (h \cdot l) = h + l \cdot (3 \cdot r + h) \approx l \cdot (3 \cdot r + h)
\end{align*}


\item Welche Werte für $l$, $r$ und $h$ sind aus Ihrer Sicht praktikabel?

Für $l$ sollte ein Wert größer $80 Bit$ gewählt werden um entsprechende Sicherheit zu gewährleisten.
Im folgenden wird $l$ deshalb mit $160 Bit$ angenommen. Die Dokumente werden vor dem Signieren ebenfalls
gehasht und haben daher $160Bit$. Es werden die oben genannten Formeln genutzt.

\vspace{0.5cm}
\begin{center}

\begin{tabular}{c|c|c}
$h$ & Speicherbedarf [MB]& Signaturgröße [kB]\\
\hline
10 & 13,11 & 9,80 \\
11 & 26,21 & 9,82 \\
12 & 52,43 & 9,84 \\
13 & 104,86 & 9,86 \\
14 & 209,72 & 9,88 \\
15 & 419,43 & 9,90 \\
16 & 838,86 & 9,92 \\
\end{tabular}
\end{center}

\vspace{0.5cm}

Ein sinnvoller Wert wäre für $h=11$.

\end{enumerate}
